<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>&lt;GTree&gt;: </title>
<meta name="generator" content="DocBook XSL Stylesheets V1.79.2">
<link rel="home" href="index.html" title="">
<link rel="up" href="ch01.html" title="GLib">
<link rel="prev" href="re72.html" title="&lt;%GLibTraverseType&gt;">
<link rel="next" href="re74.html" title="&lt;%GLibUnicodeBreakType&gt;">
<meta name="generator" content="GTK-Doc V1.33.1 (XML mode)">
<link rel="stylesheet" href="style.css" type="text/css">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table class="navigation" id="top" width="100%" summary="Navigation header" cellpadding="2" cellspacing="5"><tr valign="middle">
<td width="100%" align="left" class="shortcuts"></td>
<td><a accesskey="h" href="index.html"><img src="home.png" width="16" height="16" border="0" alt="Home"></a></td>
<td><img src="up-insensitive.png" width="16" height="16" border="0"></td>
<td><a accesskey="p" href="re72.html"><img src="left.png" width="16" height="16" border="0" alt="Prev"></a></td>
<td><a accesskey="n" href="re74.html"><img src="right.png" width="16" height="16" border="0" alt="Next"></a></td>
</tr></table>
<div class="refentry">
<a name="id-1.1.74"></a><div class="titlepage"></div>
<div class="refnamediv">
<h2>&lt;GTree&gt;</h2>
<p>&lt;GTree&gt;</p>
</div>
<div class="refsect1">
<a name="id-1.1.74.2"></a><h2>Description</h2>
<p>The GTree struct is an opaque data structure representing a
[balanced binary tree][glib-Balanced-Binary-Trees]. It should be
accessed only by using the following functions.</p>
</div>
<div class="refsect1">
<a name="id-1.1.74.3"></a><h2>Functions</h2>
<div class="refsect2">
<a name="id-1.1.74.3.2"></a><h3>destroy</h3>
<div class="informalexample"><pre class="programlisting">(define-values () (tree:destroy self))
</pre></div>
<p>Removes all keys and values from the <span class="type">GTree</span> and decreases its
reference count by one. If keys and/or values are dynamically
allocated, you should either free them first or create the <span class="type">GTree</span>
using <code class="function">g_tree_new_full()</code>. In the latter case the destroy functions
you supplied will be called on all keys and values before destroying
the <span class="type">GTree</span>.</p>
<div class="refsect3">
<a name="id-1.1.74.3.2.4"></a><h4>Parameters</h4>
<div class="informaltable"><table><tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr></table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.3"></a><h3>height</h3>
<div class="informalexample"><pre class="programlisting">(define-values (%return) (tree:height self))
</pre></div>
<p>Gets the height of a <span class="type">GTree</span>.
</p>
<p>If the <span class="type">GTree</span> contains no nodes, the height is 0.
If the <span class="type">GTree</span> contains only one root node the height is 1.
If the root node has children the height is 2, etc.</p>
<div class="refsect3">
<a name="id-1.1.74.3.3.5"></a><h4>Parameters</h4>
<div class="informaltable"><table><tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr></table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.4"></a><h3>insert</h3>
<div class="informalexample"><pre class="programlisting">(define-values () (tree:insert self key value))
</pre></div>
<p>Inserts a key/value pair into a <span class="type">GTree</span>.
</p>
<p>If the given key already exists in the <span class="type">GTree</span> its corresponding value
is set to the new value. If you supplied a <em class="parameter"><code>value_destroy_func</code></em> when
creating the <span class="type">GTree</span>, the old value is freed using that function. If
you supplied a <em class="parameter"><code>key_destroy_func</code></em> when creating the <span class="type">GTree</span>, the passed
key is freed using that function.
</p>
<p>The tree is automatically 'balanced' as new key/value pairs are added,
so that the distance from the root to every leaf is as small as possible.
The cost of maintaining a balanced tree while inserting new key/value
result in a O(n log(n)) operation where most of the other operations
are O(log(n)).</p>
<div class="refsect3">
<a name="id-1.1.74.3.4.6"></a><h4>Parameters</h4>
<div class="informaltable"><table>
<tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>key</p></td>
<td class="parameter_description">
<p>the key to insert</p>
<p>Passed as <code class="code">key</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>value</p></td>
<td class="parameter_description">
<p>the value corresponding to the key</p>
<p>Passed as <code class="code">value</code></p>
</td>
</tr>
</table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.5"></a><h3>lookup</h3>
<div class="informalexample"><pre class="programlisting">(define-values (%return) (tree:lookup self key))
</pre></div>
<p>Gets the value corresponding to the given key. Since a <span class="type">GTree</span> is
automatically balanced as key/value pairs are added, key lookup
is O(log n) (where n is the number of key/value pairs in the tree).</p>
<div class="refsect3">
<a name="id-1.1.74.3.5.4"></a><h4>Parameters</h4>
<div class="informaltable"><table>
<tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>key</p></td>
<td class="parameter_description">
<p>the key to look up</p>
<p>Passed as <code class="code">key</code></p>
</td>
</tr>
</table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.6"></a><h3>lookup-extended</h3>
<div class="informalexample"><pre class="programlisting">(define-values
  (%return orig-key value)
  (tree:lookup-extended self lookup-key))
</pre></div>
<p>Looks up a key in the <span class="type">GTree</span>, returning the original key and the
associated value. This is useful if you need to free the memory
allocated for the original key, for example before calling
<code class="function">g_tree_remove()</code>.</p>
<div class="refsect3">
<a name="id-1.1.74.3.6.4"></a><h4>Parameters</h4>
<div class="informaltable"><table>
<tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>lookup_key</p></td>
<td class="parameter_description">
<p>the key to look up</p>
<p>Passed as <code class="code">lookup-key</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>orig_key</p></td>
<td class="parameter_description">
<p>returns the original key</p>
<p>Passed as <code class="code">orig-key</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>value</p></td>
<td class="parameter_description">
<p>returns the value associated with the key</p>
<p>Passed as <code class="code">value</code></p>
</td>
</tr>
</table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.7"></a><h3>nnodes</h3>
<div class="informalexample"><pre class="programlisting">(define-values (%return) (tree:nnodes self))
</pre></div>
<p>Gets the number of nodes in a <span class="type">GTree</span>.</p>
<div class="refsect3">
<a name="id-1.1.74.3.7.4"></a><h4>Parameters</h4>
<div class="informaltable"><table><tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr></table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.8"></a><h3>ref</h3>
<div class="informalexample"><pre class="programlisting">(define-values (%return) (tree:ref self))
</pre></div>
<p>Increments the reference count of <em class="parameter"><code>tree</code></em> by one.
</p>
<p>It is safe to call this function from any thread.</p>
<div class="refsect3">
<a name="id-1.1.74.3.8.5"></a><h4>Parameters</h4>
<div class="informaltable"><table><tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr></table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.9"></a><h3>remove?</h3>
<div class="informalexample"><pre class="programlisting">(define-values (%return) (tree:remove? self key))
</pre></div>
<p>Removes a key/value pair from a <span class="type">GTree</span>.
</p>
<p>If the <span class="type">GTree</span> was created using <code class="function">g_tree_new_full()</code>, the key and value
are freed using the supplied destroy functions, otherwise you have to
make sure that any dynamically allocated values are freed yourself.
If the key does not exist in the <span class="type">GTree</span>, the function does nothing.
</p>
<p>The cost of maintaining a balanced tree while removing a key/value
result in a O(n log(n)) operation where most of the other operations
are O(log(n)).</p>
<div class="refsect3">
<a name="id-1.1.74.3.9.6"></a><h4>Parameters</h4>
<div class="informaltable"><table>
<tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>key</p></td>
<td class="parameter_description">
<p>the key to remove</p>
<p>Passed as <code class="code">key</code></p>
</td>
</tr>
</table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.10"></a><h3>remove-all</h3>
<div class="informalexample"><pre class="programlisting">(define-values () (tree:remove-all self))
</pre></div>
<p>Undocumented</p>
<div class="refsect3">
<a name="id-1.1.74.3.10.4"></a><h4>Parameters</h4>
<div class="informaltable"><table><tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr></table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.11"></a><h3>replace</h3>
<div class="informalexample"><pre class="programlisting">(define-values () (tree:replace self key value))
</pre></div>
<p>Inserts a new key and value into a <span class="type">GTree</span> similar to <code class="function">g_tree_insert()</code>.
The difference is that if the key already exists in the <span class="type">GTree</span>, it gets
replaced by the new key. If you supplied a <em class="parameter"><code>value_destroy_func</code></em> when
creating the <span class="type">GTree</span>, the old value is freed using that function. If you
supplied a <em class="parameter"><code>key_destroy_func</code></em> when creating the <span class="type">GTree</span>, the old key is
freed using that function.
</p>
<p>The tree is automatically 'balanced' as new key/value pairs are added,
so that the distance from the root to every leaf is as small as possible.</p>
<div class="refsect3">
<a name="id-1.1.74.3.11.5"></a><h4>Parameters</h4>
<div class="informaltable"><table>
<tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>key</p></td>
<td class="parameter_description">
<p>the key to insert</p>
<p>Passed as <code class="code">key</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>value</p></td>
<td class="parameter_description">
<p>the value corresponding to the key</p>
<p>Passed as <code class="code">value</code></p>
</td>
</tr>
</table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.12"></a><h3>steal?</h3>
<div class="informalexample"><pre class="programlisting">(define-values (%return) (tree:steal? self key))
</pre></div>
<p>Removes a key and its associated value from a <span class="type">GTree</span> without calling
the key and value destroy functions.
</p>
<p>If the key does not exist in the <span class="type">GTree</span>, the function does nothing.</p>
<div class="refsect3">
<a name="id-1.1.74.3.12.5"></a><h4>Parameters</h4>
<div class="informaltable"><table>
<tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>key</p></td>
<td class="parameter_description">
<p>the key to remove</p>
<p>Passed as <code class="code">key</code></p>
</td>
</tr>
</table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.13"></a><h3>unref</h3>
<div class="informalexample"><pre class="programlisting">(define-values () (tree:unref self))
</pre></div>
<p>Decrements the reference count of <em class="parameter"><code>tree</code></em> by one.
If the reference count drops to 0, all keys and values will
be destroyed (if destroy functions were specified) and all
memory allocated by <em class="parameter"><code>tree</code></em> will be released.
</p>
<p>It is safe to call this function from any thread.</p>
<div class="refsect3">
<a name="id-1.1.74.3.13.5"></a><h4>Parameters</h4>
<div class="informaltable"><table><tr>
<td class="parameter_name"><p>tree</p></td>
<td class="parameter_description">
<p>a <span class="type">GTree</span></p>
<p>Passed as <code class="code">self</code></p>
</td>
</tr></table></div>
</div>
</div>
<div class="refsect2">
<a name="id-1.1.74.3.14"></a><h3>tree:new-full</h3>
<div class="informalexample"><pre class="programlisting">(define-values
  (%return)
  (tree:new-full
    key-compare-func
    key-compare-data
    key-destroy-func
    value-destroy-func))
</pre></div>
<p>Undocumented</p>
<div class="refsect3">
<a name="id-1.1.74.3.14.4"></a><h4>Parameters</h4>
<div class="informaltable"><table>
<tr>
<td class="parameter_name"><p>key_compare_func</p></td>
<td class="parameter_description">
<p></p>
<p>Passed as <code class="code">key-compare-func</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>key_compare_data</p></td>
<td class="parameter_description">
<p></p>
<p>Passed as <code class="code">key-compare-data</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>key_destroy_func</p></td>
<td class="parameter_description">
<p></p>
<p>Passed as <code class="code">key-destroy-func</code></p>
</td>
</tr>
<tr>
<td class="parameter_name"><p>value_destroy_func</p></td>
<td class="parameter_description">
<p></p>
<p>Passed as <code class="code">value-destroy-func</code></p>
</td>
</tr>
</table></div>
</div>
</div>
</div>
</div>
<div class="footer">
<hr>Generated by GTK-Doc V1.33.1</div>
</body>
</html>
